﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <queue>

struct TreeNode 
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
	vector<vector<int>> levelOrderBottom(TreeNode* root)
	{
		vector<vector<int>> vv;
		queue<TreeNode*> q;
		int levelSize = 0;

		if (root)
		{
			q.push(root);
			levelSize = 1;
		}

		while (!q.empty())
		{
			vector<int> v;
			// 控制⼀层出完
			while (levelSize--)
			{
				TreeNode* front = q.front();
				q.pop();
				v.push_back(front->val);

				if (front->left)
					q.push(front->left);
				if (front->right)
					q.push(front->right);

			}
			// 当前层出完了，下⼀层都进队列了，队列size就是下⼀层数据个数
			levelSize = q.size();
			// 获取到每⼀层数据放到⼆维数组中
			vv.push_back(v);
		}

		reverse(vv.begin(), vv.end());

		return vv;
	}
};

int main() 
{
	// 构建二叉树 [1,2,3,4]
	TreeNode* root = new TreeNode(3);
	root->left = new TreeNode(9);
	root->right = new TreeNode(20);
	root->right->left = new TreeNode(15);
	root->right->right = new TreeNode(7);

	auto vv = Solution().levelOrderBottom(root);

	for (const auto& v : vv)
	{
		for (const auto& e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 释放二叉树内存
	delete root->right->right;
	delete root->right->left;
	delete root->right;
	delete root;

	return 0;
}